package com.lw.leetcode.back.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * hash
 * 面试题 16.22. 兰顿蚂蚁
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/14 11:33
 */
public class PrintKMoves {

    public static void main(String[] args) {
        PrintKMoves test = new PrintKMoves();

        System.out.println(Integer.MAX_VALUE);
        System.out.println(Integer.toBinaryString(0XFFFFFFFF));
        System.out.println(0XFFFFFFFF);
        long a = (1L << 32) + 1;
        System.out.println(a);
        System.out.println(Long.toBinaryString(a));
        System.out.println(a & 0XFFFFFFFFL);

        // 11111111
        int k = 5;

        List<String> list = test.printKMoves(k);
        System.out.println(list);
    }

    public List<String> printKMoves(int k) {
        char[] direction = {'L', 'U', 'R', 'D'};
        int[][] offset = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        int antDir = 2;
        Set<Long> blackSet = new HashSet<>();
        long item = (20000L << 32) + 20000;
        while (k > 0) {
            long x = (item >> 32);
            long y = (item & 0XFFFFFFFFL);
            if (blackSet.add(item)) {
                antDir = (antDir + 1) % 4;
            } else {
                antDir = (antDir + 3) % 4;
                blackSet.remove(item);
            }
            x += offset[antDir][0];
            y += offset[antDir][1];
            item = (x << 32) + y;
            k--;
        }
        long left = (item >> 32);
        long top = item & 0XFFFFFFFFL;
        long right = left;
        long bottom = top;
        for (long v : blackSet) {
            long x = (v >> 32);
            long y = v & 0XFFFFFFFFL;
            left = x < left ? x : left;
            top = y < top ? y : top;
            right = x > right ? x : right;
            bottom = y > bottom ? y : bottom;
        }
        char[][] grid = new char[(int) (bottom - top + 1)][(int) (right - left + 1)];
        for (char[] row : grid) {
            Arrays.fill(row, '_');
        }
        for (long v : blackSet) {
            grid[(int) ((v & 0XFFFFFFFFL) - top)][(int) ((v >> 32) - left)] = 'X';
        }
        grid[(int) ((item & 0XFFFFFFFFL) - top)][(int) ((item >> 32) - left)] = direction[antDir];
        List<String> result = new ArrayList<>();
        for (char[] row : grid) {
            result.add(String.valueOf(row));
        }
        return result;
    }

}
